from collections import deque
from typing import List

from LeetTool import TreeNode
from LeetTool import build_TreeNode


class Solution:
    def canMerge(self, trees: List[TreeNode]):
        # 处理只有一棵树的情况
        if len(trees) == 1:
            return trees[0]

        # 构造树的根结点的值与树的映射
        mapping = {}  # 非单结点树
        single = set()  # 单结点树
        for tree in trees:
            # 处理非单结点树
            if tree.left is not None or tree.right is not None:
                if tree.val in mapping:  # 如果非单结点树的根结点有重复，那么一定不存在有效的二叉搜索树
                    return None
                mapping[tree.val] = tree

            # 处理单结点树
            else:
                single.add(tree.val)

        # 检查单结点树是否在其他树中出现
        for tree in mapping.values():
            if tree.val in single:
                single.remove(tree.val)
            if tree.left is not None and tree.left.val in single:
                single.remove(tree.left.val)
            if tree.right is not None and tree.right.val in single:
                single.remove(tree.right.val)
        if len(single) > 0:  # 如果还有未处理的单结点树，则一定不存在有效的二叉搜索树
            return None

        # 寻找所有可能的作为根结点的树
        maybe_root = set(val for val in mapping)
        for tree in trees:
            if tree.left is not None and tree.left.val in maybe_root:
                maybe_root.remove(tree.left.val)
            if tree.right is not None and tree.right.val in maybe_root:
                maybe_root.remove(tree.right.val)

        # 如果有多个可能的作为根结点的树，那么一定不存在有效的二叉搜索树
        if len(maybe_root) > 1:
            return None

        # 如果当前没有可能的根结点，也一定不存在有效的二叉搜索树
        if len(maybe_root) == 0:
            return None

        # 确定根结点
        root = mapping[maybe_root.pop()]

        # 构造当前正在叶结点队列
        queue = deque()  # queue[i] = [叶结点的父结点,叶结点,左侧边界,右侧边界](开区间)
        if root.left is not None:
            queue.append([root, root.left, 0, root.val])
        if root.right is not None:
            queue.append([root, root.right, root.val, 50001])

        # 当前已经处理的树的集合
        visited = {root.val}

        # 遍历处理叶结点
        while queue:
            father, node1, left, right = queue.popleft()

            # 如果当前结点不存在同值的根结点
            if node1.val not in mapping:
                continue

            # 当前结点存在同值的根结点
            node2 = mapping[node1.val]

            # 替换二叉搜索树中的当前结点
            if father.left is not None and father.left.val == node1.val:
                father.left = node2
            else:
                father.right = node2

            # 检查同值的根结点的两侧子结点是否超出边界
            if node2.left is not None and node2.left.val <= left:
                return None
            if node2.right is not None and node2.right.val >= right:
                return None

            # 将左右子结点添加到叶结点队列
            if node2.left is not None:
                queue.append([node2, node2.left, left, node2.val])
            if node2.right is not None:
                queue.append([node2, node2.right, node2.val, right])

            # 记录当前已经处理的树
            visited.add(node2.val)

        # 如果还有没处理的树
        if len(visited) < len(mapping):
            return None

        return root


if __name__ == "__main__":
    # [3,2,5,1,null,4]
    print(Solution().canMerge([build_TreeNode([2, 1]), build_TreeNode([3, 2, 5]), build_TreeNode([5, 4])]))

    # []
    print(Solution().canMerge([build_TreeNode([5, 3, 8]), build_TreeNode([3, 2, 6])]))

    # []
    print(Solution().canMerge([build_TreeNode([5, 4]), build_TreeNode([3])]))

    # [2,1,3]
    print(Solution().canMerge([build_TreeNode([2, 1, 3])]))

    # 测试用例4 : None
    print(Solution().canMerge([build_TreeNode([2, 1, 3]), build_TreeNode([3, 2])]))

    # 测试用例10 :
    print(Solution().canMerge([build_TreeNode([4, 1]), build_TreeNode([1, None, 2]), build_TreeNode([2, None, 3])]))

    # 测试用例17 :
    print(Solution().canMerge([build_TreeNode([3, 2]), build_TreeNode([1]), build_TreeNode([2, None, 3])]))

